НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №5 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Лінійні однозв’язні та двозв’язні списки» Варіант № 16 Дата «19» травень 2022  Київ 2022 Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним. Завдання до лабораторної роботи: 1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту. 2. Створити двозв’язний список, вивести його. Виконати завдання згідно варіанту з двозвязним списком. Варіанти індивідуальних завдань 16. Створити стек символів. Якщо у стеці більше голосних літер – новий стек заповнити 10 одиницями, якщо ж більше голосних – новий стек заповнити двійками. Теоретичні відомості: Лінійний однозвв’язний список Лінійний список – це динамічна структура даних, кожний елемент якої за допомогою вказівника зв’язується з наступним елементом. З визначення випливає, що кожен елемент списку містить поле даних (Data) (воно може мати складну структуру) і поле посилання на наступний елемент (next). Поле посилання останнього елемента повинно містити порожній покажчик (NULL). Так як посилання лише одне (тільки на наступний елемент), то такий список є однозв’язним. Коли говорять про лінійний список, то, як правило, мають на увазі саме однозв’язний список. Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку. Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку. По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент. Хід роботи: Написано програмний код, який виконує 2 завдання. Перше – за допомогою однозв’язного списку, друге – двозв’язного. Код програми для однозв’язного списка: Посилання на код: https://replit.com/join/hpvwlgzqic-tr-15khavkin #include <iostream> #include "string" #include <fstream> #include <iostream> #include <vector> using namespace std; template <typename T> class Node { public: Node* pNext; T Data; Node(T Data = T(), Node* pNext = nullptr) { this->Data = Data; this->pNext = pNext; } }; template <typename T> class List { public: List(); ~List(); void Insert(T Value, int Index); void RemoveAt(int Index); void PopFront(); void PopBack(); void PushBack(T Data); void PushFront(T Data); void Clear(); int GetSize() const { return Size; } T& operator[](const int Index); int Search(T Data); void Show(); void DelAndSwap(T Data); private: int Size; Node<T>* Head; }; template <typename T> List<T>::List() { Size = 0; Head = nullptr; } template <typename T> List<T>::~List() { Clear(); } template <typename T> void List<T>::PushBack(T Data) { if (!Head) { Head = new Node<T>(Data); }else { Node<T>* Current = this->Head; while (Current->pNext) { Current = Current->pNext; } Current->pNext = new Node<T>(Data); } Size++; } template <typename T> T& List<T>::operator[](const int Index) { int Counter = 0; Node<T>* Current = this->Head; while (Current) { if (Counter == Index) { return Current->Data; } Current = Current->pNext; Counter++; } } template <typename T> void List<T>::PopFront() { Node<T>* Temp = Head; Head = Head->pNext; delete Temp; Size--; } template <typename T> void List<T>::PushFront(T Data) { ...